package Sort;

import java.util.LinkedList;

public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {845, 4, 54, 744, 111, 30, 6, 2};
        rSort(arr);
        arr.toString();
        System.out.println(arr);


    }
    public static void radixSort(int[] arr){
        /**
         * 1.得到数组中最大的数的位数
         */
        int max=arr[0];//假设第一数就是最大数
        for (int i=1;i<arr.length;i++){
            if (arr[i]>max){
                max=arr[i];
            }
        }
        String s = max + "";
        //得到的最大位数
        int maxLength=s.length();
        /**
         * 定义一个二维数组，表示十个桶，每个桶就是一个一维数组
         * 防止数据溢出，每一个一维数组桶，大小定义为arr.length
         */
        int[][] bucket=new int[10][arr.length];
        /**
         * 为了记录每个桶中实际存放了多少个数据，我们定义了一个一维数组来记录
         */
        int[] bucketElementCount=new int[10];
        for (int i=0,n=1;i<maxLength;i++,n*=10){
            //针对每个元素的对应位进行排序处理
            for (int j=0;j<arr.length;j++){
                //取出每个元素的对应位的值
                int digitOfElement=arr[j]/n%10;
                //放到对应的桶中
                bucket[digitOfElement][bucketElementCount[digitOfElement]]=arr[j];
                bucketElementCount[digitOfElement]++;
            }
            //
            int index=0;
            for (int k =0;k<bucketElementCount.length;k++){
                if (bucketElementCount[k]!=0){
                }
            }
        }

    }

    public static void rSort(int[] arr){
        // 1.找 分类-收集 的轮数（最大值的长度）
        int rax=getRadix(arr);
        // 2.创建桶 list所有桶的集合 每一个桶是LinkedList当成队列来用
        LinkedList<Integer>[] list=new LinkedList[10];
        for (int i=0;i<list.length;i++){
            list[i]=new LinkedList<>();
            list.toString();
        }
        // 3.开始 分类-收集
        for (int r=1;r<=rax;r++){
            //分类过程 属于哪个桶就放在哪里
            for (int i=0;i<arr.length;i++){
                int index = getIndex(arr[i], r);
                list[index].add(arr[i]);
                System.out.println("这个是list"+i+":");
                System.out.println(list[i]);
            }
            int index=0;//遍历原数组
            for (int i=0;i<list.length;i++){
                while (!list[i].isEmpty()){
                    arr[index]=list[i].poll();
                    index++;
                }
            }
        }




    }

    private static int getIndex(int num, int r) {
      int  ret=0;
      for (int i=1;i<=r;i++){
          ret=num%10;
          num/=10;
      }
      return ret;
    }

    private static int getRadix(int[] arr) {
        int max=arr[0];
        for (int i=1;i<arr.length;i++){
            if (arr[i]>max){
                max=arr[i];
            }
        }
        return (max+"").length();
    }
}
